home *** CD-ROM | disk | FTP | other *** search
/ Complete Linux / Complete Linux.iso / docs / apps / database / postgres / postgre4.z / postgre4 / src / planner / path / prune.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-08-27  |  10.8 KB  |  417 lines
  1. /*     
  2.  *      FILE
  3.  *         prune
  4.  *     
  5.  *      DESCRIPTION
  6.  *         Routines to prune redundant paths and relations
  7.  *     
  8.  */
  9.  
  10. /* RcsId("$Header: /private/postgres/src/planner/path/RCS/prune.c,v 1.20 1992/03/31 23:13:22 mer Exp $"); */
  11.  
  12. /*     
  13.  *      EXPORTS
  14.  *             prune-joinrels
  15.  *             prune-rel-paths
  16.  *             prune-rel-path
  17.  */
  18.  
  19. #include "nodes/pg_lisp.h"
  20. #include "nodes/relation.h"
  21. #include "nodes/relation.a.h"
  22.  
  23. #include "planner/internal.h"
  24. #include "planner/pathnode.h"
  25. #include "planner/prune.h"
  26.  
  27. extern int testFlag;
  28. /*    
  29.  *        prune-joinrels
  30.  *    
  31.  *        Removes any redundant relation entries from a list of rel nodes
  32.  *        'rel-list'.
  33.  *    
  34.  *        Returns the resulting list. 
  35.  *    
  36.  */
  37.  
  38. /*  .. find-join-paths, prune-joinrels    */
  39.  
  40. LispValue
  41. prune_joinrels(rel_list)
  42.      LispValue rel_list ;
  43. {
  44.      LispValue temp_list = LispNil;
  45.      if( consp(rel_list) ) {
  46.       temp_list = lispCons(CAR(rel_list),
  47.                 prune_joinrels(prune_joinrel((Rel)CAR(rel_list),
  48.                               CDR(rel_list))));
  49.      } 
  50.      return(temp_list);
  51.  
  52. }  /* function end  */
  53.  
  54. /*    
  55.  *        prune-joinrel
  56.  *    
  57.  *        Prunes those relations from 'other-rels' that are redundant with
  58.  *        'rel'.  A relation is redundant if it is built up of the same
  59.  *        relations as 'rel'.  Paths for the redundant relation are merged into
  60.  *        the pathlist of 'rel'.
  61.  *    
  62.  *        Returns a list of non-redundant relations, and sets the pathlist field
  63.  *        of 'rel' appropriately.
  64.  *    
  65.  */
  66.  
  67. /*  .. prune-joinrels, merge_joinrels */
  68.  
  69. LispValue
  70. prune_joinrel(rel,other_rels)
  71.      Rel rel;
  72.      List other_rels ;
  73. {
  74.      /*  XXX was mapcan   */
  75.      
  76.      LispValue i = LispNil;
  77.      LispValue t_list = LispNil;
  78.      LispValue temp_node = LispNil;
  79.      Rel other_rel = (Rel)NULL;
  80.      
  81.      foreach(i,other_rels) {
  82.      other_rel = (Rel)CAR(i);
  83.      if(same(get_relids(rel),get_relids(other_rel))) {
  84.          set_pathlist(rel,add_pathlist(rel,
  85.                          get_pathlist(rel),
  86.                          get_pathlist(other_rel)));
  87.          t_list = nconc(t_list, LispNil);  /* XXX is this right ? */
  88.      } 
  89.      else {
  90.          temp_node = lispCons((LispValue)other_rel,LispNil);
  91.          t_list = nconc(t_list,temp_node);
  92.      } 
  93.      }
  94.      return(t_list);
  95.  }  /* function end  */
  96.  
  97. /*    
  98.  *        prune-rel-paths
  99.  *    
  100.  *        For each relation entry in 'rel-list' (which corresponds to a join
  101.  *        relation), set pointers to the unordered path and cheapest paths
  102.  *        (if the unordered path isn't the cheapest, it is pruned), and
  103.  *        reset the relation's size field to reflect the join.
  104.  *    
  105.  *        Returns nothing of interest.
  106.  *    
  107.  */
  108.  
  109. /*  .. find-join-paths   */
  110.  
  111. void
  112. prune_rel_paths(rel_list)
  113.      List rel_list ;
  114. {
  115.     LispValue x = LispNil;
  116.     LispValue y = LispNil;
  117.     Path path;
  118.     Rel rel = (Rel)NULL;
  119.     JoinPath cheapest = (JoinPath)NULL;
  120.     
  121.     foreach(x, rel_list) {
  122.     rel = (Rel)CAR(x);
  123.     foreach(y, get_pathlist(rel)) {
  124.         path = (Path)CAR(y);
  125.         if(!get_p_ordering(path)) {
  126.         break;
  127.           }        
  128.       }
  129.     cheapest = (JoinPath)prune_rel_path(rel, path);
  130.     if(IsA(cheapest,JoinPath))
  131.     {
  132.       set_size(rel,compute_joinrel_size(cheapest));
  133.     }
  134.     else
  135.       printf( "WARN: non JoinPath called. \n");
  136.     }
  137. }  /* function end  */
  138.  
  139. /* ------------------------------
  140.  *    mergepath_contain_redundant_sorts
  141.  *
  142.  *    return true if path contains redundant sorts, i.e.,
  143.  *    a sort on an already ordered relation
  144.  *    note: current this routine is not used because
  145.  *    we forbidden any explicit sorts since hashjoins
  146.  *    can always do better.
  147.  * -------------------------------
  148.  */
  149. bool
  150. mergepath_contain_redundant_sorts(path)
  151. MergePath path;
  152. {
  153.     MergeOrder morder;
  154.     Path innerpath, outerpath;
  155.     List outerorder, innerorder;
  156.     List outerkeys, innerkeys;
  157.  
  158.     if(get_outersortkeys(path) || get_innersortkeys(path))
  159.     return true;  /* a temporary hack to reduce plan space */
  160.     else return false;
  161.  
  162. #if 0
  163.     morder = (MergeOrder)get_p_ordering(path);
  164.     outerpath = get_outerjoinpath(path);
  165.     outerorder = get_p_ordering(outerpath);
  166.     outerkeys = get_keys(outerpath);
  167.     if(outerorder && 
  168.     get_left_operator(morder) ==
  169.     (IsA(outerorder,MergeOrder)?get_left_operator(outerorder):
  170.      CInteger(CAR(outerorder))) &&
  171.     get_outersortkeys(path) &&
  172.     outerkeys &&
  173.     CAR(outerkeys) &&
  174.     member(CAR(CAR(get_outersortkeys(path))),
  175.           CAR(outerkeys)))
  176.     return true;
  177.     innerpath = get_innerjoinpath(path);
  178.     innerorder = get_p_ordering(innerpath);
  179.     innerkeys = get_keys(innerpath);
  180.     if(innerorder &&
  181.     get_right_operator(morder) ==
  182.     (IsA(innerorder,MergeOrder)?get_right_operator(innerorder):
  183.      CInteger(CAR(innerorder))) &&
  184.     get_innersortkeys(path) &&
  185.     innerkeys &&
  186.     CAR(innerkeys) &&
  187.     member(CAR(CAR(get_innersortkeys(path))),
  188.           CAR(innerkeys)))
  189.     return true;
  190.     return false;
  191. #endif
  192. }
  193.  
  194. /* --------------------------------------
  195.  *    path_contain_rotated_mergepaths
  196.  *
  197.  *    return true if two paths are virtually the same except on
  198.  *    the order of a mergejoin, such two paths should always
  199.  *    have the same cost.
  200.  * --------------------------------------
  201.  */
  202. bool
  203. path_contain_rotated_mergepaths(p1, p2)
  204. Path p1, p2;
  205. {
  206.     Path p;
  207.     if(p1 == NULL || p2 == NULL) return NULL;
  208.     if(IsA(p1,MergePath) && IsA(p2,MergePath)) {
  209.        if(equal((Node)get_outerjoinpath((JoinPath)p1),
  210.         (Node)get_innerjoinpath((JoinPath)p2)) &&
  211.            equal((Node)get_innerjoinpath((JoinPath)p1),
  212.          (Node)get_outerjoinpath((JoinPath)p2)))
  213.           return true;
  214.       }
  215.     if(IsA(p1,JoinPath) && IsA(p2,JoinPath)) {
  216.        return path_contain_rotated_mergepaths(get_outerjoinpath((JoinPath)p1),
  217.                                               get_outerjoinpath((JoinPath)p2)) ||
  218.               path_contain_rotated_mergepaths(get_innerjoinpath((JoinPath)p1),
  219.                                               get_innerjoinpath((JoinPath)p2));
  220.       }
  221.     return false;
  222. }
  223.  
  224.  
  225. /* --------------------------------------
  226.  *    path_contain_redundant_indexscans
  227.  *
  228.  *    return true if path contains obviously useless indexscans, i.e.,
  229.  *    if indxqual is nil and the order is not later utilized
  230.  * --------------------------------------
  231.  */
  232. bool
  233. path_contain_redundant_indexscans(path, order_expected)
  234. Path path;
  235. bool order_expected;
  236. {
  237.     if(IsA(path,MergePath)) {
  238.         return path_contain_redundant_indexscans(get_outerjoinpath((JoinPath)path), 
  239.                 !get_outersortkeys((MergePath)path)) ||
  240.                path_contain_redundant_indexscans(get_innerjoinpath((JoinPath)path), 
  241.                 !get_innersortkeys((MergePath)path));
  242.       }
  243.     if(IsA(path,HashPath)) {
  244.         return path_contain_redundant_indexscans(get_outerjoinpath((JoinPath)path), 
  245.                          false) ||
  246.                path_contain_redundant_indexscans(get_innerjoinpath((JoinPath)path), 
  247.                          false);
  248.       }
  249.     if(IsA(path,JoinPath)) {
  250.         if(!IsA(get_innerjoinpath((JoinPath)path),IndexPath) &&
  251.             !IsA(get_innerjoinpath((JoinPath)path),JoinPath) &&
  252.             length(get_relids(get_parent((Path)get_innerjoinpath((JoinPath)path)))) == 1)
  253.            return true;
  254.         return path_contain_redundant_indexscans(get_outerjoinpath((JoinPath)path), 
  255.                          order_expected) ||
  256.                path_contain_redundant_indexscans(get_innerjoinpath((JoinPath)path), 
  257.                          false);
  258.       }
  259.     if(IsA(path,IndexPath)) {
  260.         return lispNullp(get_indexqual((IndexPath)path)) && !order_expected;
  261.       }
  262.     return false;
  263. }
  264.  
  265. /* ----------------------------------------------
  266.  *    test_prune_unnecessary_paths
  267.  *
  268.  *    prune paths of rel for tests, only meant to be called with
  269.  *    testFlag is set.
  270.  * -----------------------------------------------
  271.  */
  272. void
  273. test_prune_unnecessary_paths(rel)
  274. Rel rel;
  275. {
  276.      LispValue x, y;
  277.      Path path, path1;
  278.      List newpathlist = LispNil;
  279.      List prunelist = LispNil;
  280.      /* done in path generation, match_unsorted_outer and match_unsorted_inner
  281.      foreach(x, get_pathlist(rel)) {
  282.      path = (Path)CAR(x);
  283.      if(IsA(path,MergePath)) {
  284.          if(mergepath_contain_redundant_sorts(path))
  285.          continue;
  286.        }
  287.      newpathlist = nappend1(newpathlist, path);
  288.       }
  289.      */
  290.      foreach(x, get_pathlist(rel)) {
  291.      path = (Path)CAR(x);
  292.      if(!path_contain_redundant_indexscans(path,
  293.                 (length(get_relids(get_parent(path))) !=
  294.                  length(_base_relation_list_)))) {
  295.          newpathlist = nappend1(newpathlist, (LispValue)path);
  296.        }
  297.        }
  298.      foreach(x, newpathlist) {
  299.      path = (Path)CAR(x);
  300.      foreach(y, CDR(x)) {
  301.          path1 = (Path)CAR(y);
  302.          if(equal((Node)path, (Node)path1) ||
  303.          path_contain_rotated_mergepaths(path, path1))
  304.          prunelist = nappend1(prunelist, (LispValue)path1);
  305.        }
  306.        }
  307.      newpathlist = nset_difference(newpathlist, prunelist);
  308.      set_pathlist(rel, newpathlist);
  309. }
  310.  
  311. /*    
  312.  *        prune-rel-path
  313.  *    
  314.  *        Compares the unordered path for a relation with the cheapest path  if
  315.  *        the unordered path is not cheapest, it is pruned.
  316.  *    
  317.  *        Resets the pointers in 'rel' for unordered and cheapest paths.
  318.  *    
  319.  *        Returns the cheapest path.
  320.  *    
  321.  */
  322.  
  323. /*  .. find-rel-paths, prune-rel-paths     */
  324.  
  325. Path
  326. prune_rel_path(rel,unorderedpath)
  327.      Rel rel ;
  328.      Path unorderedpath ;
  329. {
  330.      Path cheapest = set_cheapest(rel,get_pathlist(rel));
  331.  
  332.      if(!(eq(unorderedpath,cheapest)) && !testFlag) {
  333.  
  334.       set_unorderedpath(rel,(PathPtr)NULL);
  335.       set_pathlist(rel,LispRemove((LispValue)unorderedpath,
  336.                       get_pathlist(rel)));
  337.  
  338.      } else {
  339.  
  340.       set_unorderedpath(rel,(PathPtr)unorderedpath);
  341.  
  342.      } 
  343.  
  344.      if(testFlag) {
  345.      test_prune_unnecessary_paths(rel);
  346.        }
  347.      
  348.      return(cheapest);
  349.  
  350. }  /* function end  */
  351.  
  352.  
  353. /*
  354.  *      merge-joinrels
  355.  *
  356.  *      Given two lists of rel nodes that are already
  357.  *      pruned, merge them into one pruned rel node list
  358.  *
  359.  *      'rel-list1' and
  360.  *      'rel-list2' are the rel node lists
  361.  *
  362.  *      Returns one pruned rel node list
  363.  */
  364.  
  365. /* .. find-join-paths
  366. */
  367. LispValue
  368. merge_joinrels(rel_list1,rel_list2)
  369. LispValue rel_list1, rel_list2;
  370. {
  371.     LispValue xrel = LispNil;
  372.  
  373.     foreach(xrel,rel_list1) {
  374.         Rel rel = (Rel)CAR(xrel);
  375.         rel_list2 = prune_joinrel(rel,rel_list2);
  376.     }
  377.     return(append(rel_list1, rel_list2));
  378. }
  379.  
  380. /*
  381.  *    prune_oldrels
  382.  *
  383.  *    If all the joininfo's in a rel node are inactive,
  384.  *    that means that this node has been joined into
  385.  *    other nodes in all possible ways, therefore
  386.  *    this node can be discarded.  If not, it will cause
  387.  *    extra complexity of the optimizer.
  388.  *
  389.  *    old_rels is a list of rel nodes
  390.  *    
  391.  *    Returns a new list of rel nodes
  392.  */
  393.  
  394. /* .. find_join_paths
  395. */
  396. LispValue
  397. prune_oldrels(old_rels)
  398. LispValue old_rels;
  399. {
  400.      Rel rel;
  401.      LispValue joininfo_list, xjoininfo;
  402.  
  403.      if(old_rels == LispNil)
  404.       return(LispNil);
  405.  
  406.      rel = (Rel)CAR(old_rels);
  407.      joininfo_list = get_joininfo(rel);
  408.      if(joininfo_list == LispNil)
  409.      return(lispCons((LispValue)rel, prune_oldrels(CDR(old_rels))));
  410.      foreach(xjoininfo, joininfo_list) {
  411.      JInfo joininfo = (JInfo)CAR(xjoininfo);
  412.      if(!joininfo_inactive(joininfo))
  413.           return(lispCons((LispValue)rel, prune_oldrels(CDR(old_rels))));
  414.       }
  415.      return(prune_oldrels(CDR(old_rels)));
  416. }
  417.